package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 739. 每日温度
 * @date 2025/2/13 10:35
 */
public class E739 {

    /**
     * <h3>方法一：维护一个单调递增栈（从栈顶到栈底），越往栈顶的温度越新</h3>
     *
     * @param temperatures 温度数组
     * @return 每日温度
     */
    public int[] dailyTemperatures(int[] temperatures) {
        // 1. 初始化答案数组
        int[] answer = new int[temperatures.length];
        // 2. 准备单调栈，存储的是温度数组的索引
        LinkedList<Integer> stack = new LinkedList<>();
        // 3. 遍历温度数组，while(如果当前温度大于栈顶温度，则出栈)，并记录答案，将当前温度入栈到合适位置
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                Integer index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i); // 当前温度小于栈顶温度，入栈
        }
        return answer;
    }
}
